// class Solution {
//     int tmp[50010];
// public:
//     int reversePairs(vector<int>& record) {
//         return MergeSort(record,0,record.size()-1);
//     }

//     int MergeSort(vector<int>& record,int begin,int end)
//     {
//         if(begin>=end) return 0;
//         int mid=(begin+end)/2;

//         int ret=0;
//         ret+=MergeSort(record,begin,mid);
//         ret+=MergeSort(record,mid+1,end);

//         //处理一左一右
//         int begin1=begin,end1=mid;
//         int begin2=mid+1,end2=end;
//         int j=0;
//         while(begin1<=end1&&begin2<=end2)
//         {
//             if(record[begin1]<=record[begin2])
//             {
//                 //处理排序，顺便让begin1向后遍历
//                 tmp[j++]=record[begin1++];
//             }
//             else
//             {
//                 ret+=(mid-begin1+1);
//                 tmp[j++]=record[begin2++];
//             }
//         }
//         while(begin1<=end1)  tmp[j++]=record[begin1++];
//         while(begin2<=end2)  tmp[j++]=record[begin2++];

//         for(int i=begin;i<=end;i++)
//         record[i]=tmp[i-begin];
//         return ret;
//     }
// };

class Solution {
    int tmp[50010];
public:
    int reversePairs(vector<int>& record) {
        return MergeSort(record,0,record.size()-1);
    }

    int MergeSort(vector<int>& record,int begin,int end)
    {
        if(begin>=end) return 0;
        int mid=(begin+end)/2;

        int ret=0;
        ret+=MergeSort(record,begin,mid);
        ret+=MergeSort(record,mid+1,end);

        //处理一左一右
        int begin1=begin,end1=mid;
        int begin2=mid+1,end2=end;
        int j=0;
        while(begin1<=end1&&begin2<=end2)
        {
            if(record[begin1]<=record[begin2])
            {
                tmp[j++]=record[begin2++];
            }
            else
            {
                ret+=(end-begin2+1);
                tmp[j++]=record[begin1++];
            }
        }
        while(begin1<=end1)  tmp[j++]=record[begin1++];
        while(begin2<=end2)  tmp[j++]=record[begin2++];

        for(int i=begin;i<=end;i++)
        record[i]=tmp[i-begin];
        return ret;
    }
};